package com.shuzijun.leetcode.editor.cn;

import java.util.HashMap;

public class QingWaTiaoTaiJieWenTiLcof{
    public static void main(String[] args) {
         Solution solution = new QingWaTiaoTaiJieWenTiLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private int mod = 1000000007;
    private HashMap<Integer, Integer> memo = new HashMap<>();
        public int numWays(int n) {
            if (n == 0) return 1;
            if (n == 1) return 1;
            if (memo.containsKey(n)){
                return memo.get(n);
            }
            int ret = (numWays(n - 1) + numWays(n - 2)) % mod;
            memo.put(n,ret);
            return ret;
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}